package com.shuang.tree24;

public class CountNodes {

    /**
     * 针对完全二叉树的解法
     *
     完全二叉树 向下遍历时 肯定会遇到一个子树是满二叉树
     * 满二叉树的结点数为：2^depth - 1
     */
    //递归实现
    public int countNodes(TreeNode root) {

        if (root == null){
            return 0;
        }

        //判断是否是满二叉树方法：左右遍历走到最后一个节点时 左右深度一样
        // 用于计算深度 初始为零 为了后序次方的计算方便
        int leftDepth = 0;
        int rightDepth = 0;

        TreeNode leftNode = root.left;
        TreeNode rightNode = root.right;

        while (leftNode != null){
            leftNode = leftNode.left;
            leftDepth++;
        }

        while (rightNode != null){
            rightNode = rightNode.right;
            rightDepth++;
        }

        //是满二叉树 用公式计算节点数
        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }

        //不是满二叉树 递归到下一个子树判断是否是二叉树 后序 左右中
        int leftCountNodes = countNodes(root.left); //左
        int rightCountNodes = countNodes(root.right); //右
        int result = leftCountNodes + rightCountNodes + 1;  //中

        return result;

    }
}
